package acwing._1_1AlgorithmBasic;

/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic.AlgorithmTemplate
 * @File : _2_7Hash.java
 * @Author : WangRuoyu
 * @Date : 2023/4/1 9:24
 */

public class _2_7Hash {

    // 哈希表 拉链法解决哈希冲突
    static final int MOD = 100003;
    static int[] h = new int[MOD];
    static int[] e = new int[MOD];
    static int[] ne = new int[MOD];
    static int idx = 0;

    static void insert(int x) {
        int k = (x % MOD + MOD) % MOD;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx;
        idx++;
    }

    static boolean find(int x) {
        int k = (x % MOD + MOD) % MOD;
        for (int i = h[k]; i != -1; i = ne[i]) {
            if (e[i] == x) {
                return true;
            }
        }
        return false;
    }

    static final int MOD2 = 200003;
    static int[] h2 = new int[MOD2];

    static int find2(int x) {
        int k = (x % MOD2 + MOD2) % MOD2;
        while (h2[k] != Integer.MIN_VALUE && h2[k] != x) {
            k++;
            if (k >= MOD2) {
                k = 0;
            }
        }
        return k;
    }

    // 字符串哈希
    static int n;
    static final int N = 100010;
    static long[] h3 = new long[N];
    static long[] p = new long[N];
    static final int P = 131;

    static void init(String str) {
        p[0] = 1;
        for (int i = 1; i <= n; ++i) {
            h3[i] = h3[i - 1] * P + str.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
    }

    static long get(int l, int r) {
        return h3[r] - h3[l - 1] * p[r - l + 1];
    }
}
